Our algorithms for network flow show that, if all edge capacities are integral, then there always
exists an integral maximum flow. Show by example that some network flow instances with
integral edge capacities also have non-integral (rational, even irrational) optimal solutions.

\vspace{10pt}

Let's consider the following example of flow network:

\input{p4_f1.tex}

Here numbers near the edges mean the capacities of them.

The minimum cut of that network contains only one edge with capacity $1$, and, thus, the maximum flow value is $1$.

There are a lot of ways to assign flow to edges and get the flow of cost $1$.

For example, with possible rational assignments for $\forall n \in \mathbb{N}, n \ge 2$ the following flow assignment will have the maximum cost:

\input{p4_f2.tex}

If we can use irrational assignments, then the flow assignment of the following structure gives maximum flow for $\forall a,n \in \mathbb{N}, \; n > \sqrt{a}$:

\input{p4_f3.tex}

So in the network with integral capacities of all edges can be optimal flows with non-integral assignments to edges. However, it is obvious, that there is always at least one edge with integral assignment (as all edges of minimum cut have to be saturated and, thus, have integral assignment of flow). 